package cn.edu.njust.alg.leetcode;

import java.util.Stack;

/*
 * 中缀表达式转换成后缀表达式并求值
 * 
 * 中缀表达式转后缀表达式的方法：
 1.遇到操作数：直接输出（添加到后缀表达式中）
 2.栈为空时，遇到运算符，直接入栈
 3.遇到左括号：将其入栈
 4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
 5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
 6.最终将栈中的元素依次出栈，输出。
 */

public class Leetcode_227_Basic_CalculatorII {

	public static int calculate(String s) {
		long op1 = 0, op2 = 0;
		StringBuffer sb = new StringBuffer();
		Stack<Long> ns = new Stack<Long>();
		Stack<Character> ops = new Stack<Character>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == ' ') {
				continue;
			}
			switch (c) {
			case '+':
			case '-':
			case '*':
			case '/':
				sb.append(op2 + " ");
				if (ops.isEmpty()) {
					ops.push(c);
				} else {
					while (!ops.isEmpty() && Precedence(c, ops.peek()) <= 0) {
						sb.append(ops.pop());
					}
					ops.push(c);
				}
				op2 = 0;
				break;
			default:
				op2 = op2 * 10 + (c - '0');
				break;
			}
		}
		sb.append(op2 + " ");
		while (!ops.empty()) {
			sb.append(ops.pop());
		}
		op2 = 0;
		for (int i = 0; i < sb.length(); i++) {
			char c = sb.charAt(i);
			switch (c) {
			case ' ':
				ns.push(op2);
				op2 = 0;
				break;
			case '+':
			case '-':
			case '*':
			case '/':
				op2 = ns.pop();
				op1 = ns.pop();
				op2 = calc(op1, op2, c);
				ns.push(op2);
				op2 = 0;
				break;
			default:
				op2 = op2 * 10 + (c - '0');
				break;
			}
		}

		return (int)(long)ns.pop();
	}

	public static int Precedence(char op1, char op2) {
		if (op1 == '(') {
			return -1;
		}

		if (op1 == '+' || op1 == '-') {
			if (op2 == '*' || op2 == '/') {
				return -1;
			} else {
				return 0;
			}
		}

		if (op1 == '*' || op1 == '/') {
			if (op2 == '+' || op2 == '-') {
				return 1;
			} else {
				return 0;
			}
		}
		return 0;
	}

	public static long calc(long op1, long op2, Character character) {
		long res = 0;
		switch (character) {
		case '+':
			res = op1 + op2;
			break;
		case '-':
			res = op1 - op2;
			break;
		case '*':
			res = op1 * op2;
			break;
		case '/':
			res = op1 / op2;
			break;
		default:
			break;
		}
		return res;
	}

	public static void main(String[] args) {

		System.out
				.println(calculate("0-2147483648"));
	}

}
